package leetcode;

import java.util.ArrayList;

public class Q0057 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        ArrayList<int[]> list = new ArrayList<>();
        int l = newInterval[0], r = newInterval[1];
        int k = 0;
        while (k < intervals.length && intervals[k][1] < l) {
            list.add(intervals[k++]);
        }
        if (k < intervals.length) l = Math.min(l, intervals[k][0]);

        while (k < intervals.length && r >= intervals[k][0]) {
            r = Math.max(r, intervals[k][1]);
            k++;
        }
        list.add(new int[]{l, r});

        while (k < intervals.length) {
            list.add(intervals[k++]);
        }

        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}
